package sort.冒泡排序;

public class MaoPao {
    /**
     * 冒泡排序,将最大元素移动到最后
     */
    public static void test1() {
        int[] array = {25,17,9,45,79,0,64,18};
        for(int begin =1;begin < array.length;begin ++ ) {
            if (array[begin]<array[begin-1]) {
                int temp = array[begin];
                array[begin] = array[begin-1];
                array[begin-1] = temp;
            }
        }
        for (int i : array) {
            System.out.println(i);
        }
    }
    /**
     * 找规律，循环移动,外层的结束索引不断的减，内层的开始索引不断的增加
     */
    public static void test2() {
        int[] array = {25,17,9,45,79,0,64,18};
        for (int end = array.length;end >1;end-- ) {
            for(int begin =1;begin < end;begin ++ ) {
                if (array[begin]<array[begin-1]) {
                    int temp = array[begin];
                    array[begin] = array[begin-1];
                    array[begin-1] = temp;
                }
            }
        }
        for (int i : array) {
            System.out.println(i);
        }
    }

    public static void main(String[] args) {
        int[] array = {25,17,9,45,79,0,64,18};
        sort(array);
        for (int i : array) {
            System.out.println(i);
        }
    }

    public static int[] sort(int[] arrays) {
        for(int end = arrays.length;end > 0;end--) {
            for(int begin = 1;begin < end;begin ++) {
                if(arrays[begin] < arrays[begin-1]) {
                    int temp = arrays[begin];
                    arrays[begin] = arrays[begin-1];
                    arrays[begin-1] = temp;
                }
            }
        }
        return arrays;
    }
    /**
     * 优化
     * 原来的：不管有序无序，都会进行两层循环，如果序列有序可以提前结束循环
     * 如果内层循环没有交换元素位置，说明数组完全有序
     */
    public static void test3() {
        int[] array = {25,17,9,45,79,0,64,18};
        for (int end = array.length;end >1;end-- ) {
            boolean flag = true;
            for(int begin =1;begin < end;begin ++ ) {
                if (array[begin]<array[begin-1]) {
                    int temp = array[begin];
                    array[begin] = array[begin-1];
                    array[begin-1] = temp;
                    flag = false;
                }
            }
            if (flag) {break;}
        }
        for (int i : array) {
            System.out.println(i);
        }
    }
    /**
     * 冒泡排序优化二
     * 完全提前有序概率会很低
     * 如果序列尾部已经局部有序，可以记录最后一次交换的位置，减少比较次数
     * 为了便于理解，begin与end为数据下标。
     * 最坏平均时间复杂度O(n2)
     * 最好的平均时间复杂度O(n)
     */
    public static void test4() {
        int[] array = {25,17,9,45,79,0,64,18};
        for (int end = array.length-1;end >1;end-- ) {
            // 记录最后一次交换的位置
            int index = 0;
            for(int begin =1;begin <= end;begin ++ ) {
                if (array[begin]<array[begin-1]) {
                    int temp = array[begin];
                    array[begin] = array[begin-1];
                    array[begin-1] = temp;
                    index = begin;
                }
            }
            end = index;
        }
        for (int i : array) {
            System.out.println(i);
        }
    }
}
